package com.love.dynamicPlan;


/**
 * 1137. 第 N 个泰波那契数
 * 泰波那契序列 Tn 定义如下：
 *
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 *
 * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
 *
 * 示例 1：
 *
 * 输入：n = 4
 * 输出：4
 * 解释：
 * T_3 = 0 + 1 + 1 = 2
 * T_4 = 1 + 1 + 2 = 4
 * 示例 2：
 *
 * 输入：n = 25
 * 输出：1389537
 */
public class TBonacciNumber {


    public static int sum(int N){
        int[] dp = new int[N + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;

        for (int k = 3; k <= N; k++) {
            dp[k] = dp[k - 3] + dp[k - 2] + dp[k - 1];
        }

        return dp[N];
    }


    public static void main(String[] args) {
        System.out.println(sum(25));
    }

}
